Satellites provide important services in peoples' daily lives, such as communication (e.g., satellite phones), navigation (e.g., Global Positioning System (GPS)), surveillance, weather forecasting/monitoring, to name just a few. In some cases, a satellite service may be provided by a constellation of multiple satellites that collectively cover a desired service area. For example, the ubiquitous GPS service is provided by a constellation of satellites operated by the United States government, which is committed to maintaining the availability of at least 24 operational GPS satellites, 95% of the time. To achieve this goal, the government has been flying 31 operational GPS satellites for the past few years, according to http://www.gps.gov.
Existing satellite scheduling may focus on connection-oriented services, addressing single satellite and single orbit solutions. In addressing this scenario, the scheduling approach can assess one or more feasible sets of requests and then schedule the requests, optimizing the jobs over satellites and times. The scheduling of satellite services can be on a first in first out (FIFO) or priority queue basis, where constraints applied typically include time constraints and on-board resource constraints.